//There is an integer array nums sorted in ascending order (with distinct 
//values). 
//
// Prior to being passed to your function, nums is possibly rotated at an 
//unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k]
//, nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For 
//example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0
//,1,2]. 
//
// Given the array nums after the possible rotation and an integer target, 
//return the index of target if it is in nums, or -1 if it is not in nums. 
//
// You must write an algorithm with O(log n) runtime complexity. 
//
// 
// Example 1: 
// Input: nums = [4,5,6,7,0,1,2], target = 0
//Output: 4
// Example 2: 
// Input: nums = [4,5,6,7,0,1,2], target = 3
//Output: -1
// Example 3: 
// Input: nums = [1], target = 0
//Output: -1
// 
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5000 
// -10⁴ <= nums[i] <= 10⁴ 
// All values of nums are unique. 
// nums is an ascending array that is possibly rotated. 
// -10⁴ <= target <= 10⁴ 
// 
// Related Topics Array Binary Search 👍 11122 👎 788


package leetcode.editor.en;

import jdk.nashorn.internal.ir.IfNode;

public class _33_SearchInRotatedSortedArray {
    public static void main(String[] args) {
        Solution solution = new _33_SearchInRotatedSortedArray().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            int l = 0, r = nums.length-1;
            while (l<r){
                int mid = l + (r - l) / 2;
                if (nums[l]<=nums[mid]) {
                    if (nums[l]<=target && target<=nums[mid]) {
                        r = mid;
                    }else {
                        l = mid+1;
                    }
                }else {
                    if (nums[mid]<target && target<=nums[r]) {
                        l = mid+1;
                    }else {
                        r = mid;
                    }
                }
            }

            if (nums[l] == target) {
                return l;
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}